// 请判断一个链表是否为回文链表。

// 使用栈的解法
const isPalindrome_linklist_stack = function (head: ListNode | null): boolean {
    const stack: number[] = [];// 辅助栈
    let curr: ListNode | null = head;// 当前指针
    // 将链表值记录在栈中
    while (curr !== null) {
        stack.push(curr.val);
        curr = curr.next;
    }
    // 计算中点索引
    let midIndex = Math.floor(stack.length / 2);
    curr = head;// 重新赋值当前指针
    // 检验回文
    for (let i = 0; i < midIndex; i++) {
        if (curr && stack.pop() !== curr.val) {
            return false;
        }
        curr = curr!.next;
    }
    return true;
};


// 使用递归的解法
const isPalindrome_linklist_recursion = function (head: ListNode | null): boolean {
    let curr: ListNode | null = head; // 当前指针-->需要作为闭包变量
    // 辅助递归函数
    const isPalindrome_recursion = function (traverseCurr: ListNode | null): boolean {
        if (traverseCurr === null || curr === null) {// 可以利用系统栈倒序输出链表
            return true;
        }
        // 在指针前移前，储存当前的判断值
        const currJudge = isPalindrome_recursion(traverseCurr.next) && (traverseCurr.val === curr.val);
        curr = curr.next;
        return currJudge;
    };

    return isPalindrome_recursion(head);
};



// 这道题也是一道有意思的例题
// 首先借用数据结构的解法，我们可以轻易想到一切回文类的判断都可以使用辅助栈来进行求解
// 只需要用栈记录变量，然后再走一遍链表依次判断即可
// 求解到这里其实还可以想到一个比较巧妙的方法
// 就是我们其实是可以通过递归的方式来实现链表的逆序输出的（实质上是利用了系统栈）
// 我们存储一个外部变量，然后通过递归倒序输出链表的值，
// 在每轮递归的比较后，暂时存储当前的比较结果，然后当前正序指针后移
// 再返回比较结果即可实现一层递归的判断，我们让这个判断结果通过递归的&&运算实现穿透性
// 也是值得学习的一种解法。
// 此外还存在一种最优解法，其实是可以通过快慢指针找到链表的中点，断链反转半链表
// 再依次比较，也可以实现回文链表的判断，性能可以达到空间O1，时间On
// 但在代码的书写上就比较容易带来一些难度。